package util;

import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArraySet;

/**
 * Index of a collection. Elements are grouped by index (not unique key or group). Index is slow to create and modify but can improve performance if search by
 * index is intensive operation and modifications are rare. Thread safe due to {@link ConcurrentHashMap} and {@link CopyOnWriteArraySet} usage.
 * <p>
 * Once created insure index is updating according to original collection updates.
 * <p>
 * Supports the notion of the 'not indexed elements' - null index.
 * 
 * @param <Idx>
 *            non unique key or group
 * @param <V>
 * @see TwoDimmIndex
 * @author Mykhaylo Adamovych
 */
public class Index<Idx, V> {
    public static class TwoDimmIndex<Idx1, Idx2, V> {
        protected final Predicate<V, Idx1> predicateOfTheIndex1;
        protected final Predicate<V, Idx2> predicateOfTheIndex2;
        protected final Object addRemoveLock = new Object();
        protected final Map<Idx1, Index<Idx2, V>> twoDImmIndex = new ConcurrentHashMap<Idx1, Index<Idx2, V>>();
        protected final Index<Idx2, V> indexForNulls;
        
        public TwoDimmIndex(Predicate<V, Idx1> predicateOfTheIndex1, Predicate<V, Idx2> predicateOfTheIndex2) {
            this.predicateOfTheIndex1 = predicateOfTheIndex1;
            this.predicateOfTheIndex2 = predicateOfTheIndex2;
            indexForNulls = new Index<Idx2, V>(predicateOfTheIndex2);
        }
        
        public boolean add(V value) {
            if (value == null)
                return false;
            final Idx1 idx1 = predicateOfTheIndex1.evaluate(value);
            if (idx1 == null)
                return indexForNulls.add(value);
            synchronized (addRemoveLock) {
                Index<Idx2, V> oneDimmIndex = twoDImmIndex.get(idx1);
                if (oneDimmIndex == null) {
                    oneDimmIndex = new Index<Idx2, V>(predicateOfTheIndex2);
                    twoDImmIndex.put(idx1, oneDimmIndex);
                }
                return oneDimmIndex.add(value);
            }
        }
        
        public Set<V> get(Idx1 idx1, Idx2 idx2) {
            if (idx1 == null)
                return indexForNulls.get(idx2);
            final Index<Idx2, V> oneDimmIndex = twoDImmIndex.get(idx1);
            if (oneDimmIndex == null)
                return null;
            return oneDimmIndex.get(idx2);
        }
        
        public Set<Idx1> keySet() {
            return twoDImmIndex.keySet();
        }
        
        public boolean remove(V value) {
            final Idx1 idx1 = predicateOfTheIndex1.evaluate(value);
            if (idx1 == null)
                return indexForNulls.remove(value);
            boolean removed = false;
            synchronized (addRemoveLock) {
                final Index<Idx2, V> oneDimmIndex = twoDImmIndex.get(idx1);
                if (oneDimmIndex == null)
                    return false;
                removed = oneDimmIndex.remove(value);
                if (removed && oneDimmIndex.keySet().size() == 0)
                    twoDImmIndex.remove(idx1);
            }
            return removed;
        }
        
        public void update(V oldValue, V newValue) {
            if (oldValue == null && newValue == null)
                return;
            if (oldValue == null)
                add(newValue);
            else if (newValue == null)
                remove(oldValue);
            else if (!predicateOfTheIndex1.evaluate(oldValue).equals(predicateOfTheIndex1.evaluate(newValue))
                    || !predicateOfTheIndex1.evaluate(oldValue).equals(predicateOfTheIndex1.evaluate(newValue))) {
                remove(oldValue);
                add(newValue);
            }
        }
    }
    
    protected final Predicate<V, Idx> predicateOfTheIndex;
    /**
     * To make remove atomic operation and prevent data loss.
     */
    protected final Object addRemoveLock = new Object();
    protected final Map<Idx, Set<V>> index = new ConcurrentHashMap<Idx, Set<V>>();
    /**
     * Needed because of ConcurrentHashMap doesn't support null keys.
     */
    protected final Set<V> indexForNulls = new CopyOnWriteArraySet<V>();
    
    /**
     * @param predicateOfTheIndex
     *            algorithm to calculate index key for dummy value.
     */
    public Index(Predicate<V, Idx> predicateOfTheIndex) {
        this.predicateOfTheIndex = predicateOfTheIndex;
    }
    
    /**
     * Adds value to index.
     * 
     * @param value
     * @return true if this set did not already contain the specified element
     */
    public boolean add(V value) {
        if (value == null)
            return false;
        final Idx idx = predicateOfTheIndex.evaluate(value);
        if (idx == null)
            return indexForNulls.add(value);
        synchronized (addRemoveLock) {
            Set<V> keys = index.get(idx);
            if (keys == null) {
                keys = new CopyOnWriteArraySet<V>();
                index.put(idx, keys);
            }
            final boolean result = keys.add(value);
            return result;
        }
    }
    
    /**
     * Returns values set of specified index. Fast and tread safe due to {@link ConcurrentHashMap} and {@link CopyOnWriteArraySet} usage. No additional
     * synchronization needed to iterate through result set.
     * 
     * @param key
     *            index key or null as of valid key
     * @return {@link CopyOnWriteArraySet thread save set} to iterate through.
     */
    public Set<V> get(Idx key) {
        if (key == null)
            return indexForNulls;
        return index.get(key);
    }
    
    /**
     * Set of index keys. Null index is not included.
     * 
     * @see Map#keySet()
     */
    public Set<Idx> keySet() {
        return index.keySet();
    }
    
    /**
     * Removes value from index.
     * 
     * @param value
     * @return true if this index contained the specified element
     */
    public boolean remove(V value) {
        final Idx idx = predicateOfTheIndex.evaluate(value);
        if (idx == null)
            return indexForNulls.remove(value);
        boolean removed = false;
        synchronized (addRemoveLock) {
            final Set<V> values = index.get(idx);
            if (values == null)
                return false;
            removed = values.remove(value);
            if (removed && values.size() == 0)
                index.remove(idx);
        }
        return removed;
    }
    
    /**
     * Updates index only if key have changed. Accepts nulls.
     * 
     * @param oldValue
     * @param newValue
     */
    public void update(V oldValue, V newValue) {
        if (oldValue == null && newValue == null)
            return;
        if (oldValue == null)
            add(newValue);
        else if (newValue == null)
            remove(oldValue);
        else if (!predicateOfTheIndex.evaluate(oldValue).equals(predicateOfTheIndex.evaluate(newValue))) {
            remove(oldValue);
            add(newValue);
        }
    }
}